package com.fitc.treestructure;

/*
 * Adapted from original code at http://www.quesucede.com/page/show/id/java_tree_implementation 
 * which is: Copyright (C) 2007-2012 by Brett Alistair Kromkamp <brett@polishedcode.com>.
 * 
 * Code below shares little or nothing with original code so not sure what copyright issues are..
 * 
 */


import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;

public class StringTree implements Iterable<Node> {

    private ArrayList<Node> _nodes;
    private TraversalStrategy _traversalStrategy;
	private String _letterSequence;
    
    // constructors
    public StringTree() {
    	
        this(TraversalStrategy.BREADTH_FIRST);
        Node.INDEX = -1;
    }

    public StringTree(TraversalStrategy traversalStrategy) {
        _nodes = new ArrayList<Node>();
        _traversalStrategy = traversalStrategy;
    }

    // properties
    public ArrayList<Node> getNodes() {
        return _nodes;
    }

    public TraversalStrategy getTraversalStrategy() {
        return _traversalStrategy;
    }

    public void setTraversalStrategy(TraversalStrategy traversalStrategy) {
        _traversalStrategy = traversalStrategy;
    }

    public Node createNode(String identifier) {
        return this.createNode(identifier, null);
    }


    public Node createNode(String identifier,Node parent) {
    	  Node node = new Node(identifier);
    	if (parent==null){
    		node.setLetterDepth(identifier.length());
    	} else {
    		node.setLetterDepth(parent.getLetterDepth() + identifier.length());
    	}
    	
      
    
        _nodes.add(node);

        
        this.setParentPointer(node,parent);
        this.setForwardPointer(node, parent);

        return node;
    }

	private void setParentPointer(Node node,Node parent ) {
		if (parent!=null){
        	_nodes.get(node.getIndex()).setParentPointer(parent.getIndex());
        } else {
        	_nodes.get(node.getIndex()).setParentPointer(-1);
        }
	}

	public int size() {
        return _nodes.size();
    }

    public Iterator<Node> iterator() {
        return _traversalStrategy == TraversalStrategy.BREADTH_FIRST 
            ? new BreadthFirstTreeIterator(_nodes) : new DepthFirstTreeIterator(_nodes);
    }

    // private
    private void setForwardPointer(Node node, Node parent) {
        if (parent != null) {
            int parentIndex = parent.getIndex();
            _nodes.get(parentIndex).addForwardPointer(node.getIndex());
        }
    }
    
    
    //
    public List<Node> getLeaves(boolean fit){
    	Iterator<Node> i = this.iterator();
		List<Node> leaves = new ArrayList<Node>();
		while (i.hasNext()){
			Node n = i.next();
			if (n.getForwardPointers().size()==0){
			
				if (!fit || n.getLetterDepth()==_letterSequence.length()){  
					leaves.add(n);
				}
			} 
		}
		return leaves;
    }
    
    public List<Path> getPaths(boolean fit){
    	List<Node> leaves = getLeaves(fit);
    	List<Path> paths = new ArrayList<Path>();
    	
    	
    	for (Node l: leaves){
    		Path p = new Path();
    		p.add(l); // add leaf to path
    		Node n = l;
    		while (n.hasParent()){
	    		n = _nodes.get(n.getParentPointer());
	    		p.add(n);
    		}
    		p.getSd();
    		Collections.reverse(p); //reverse to path is top-down
    		paths.add(p);
    	}
    	
    	return paths;
    }
    
    public List<Path> getPaths(){
    	return this.getPaths(false);
    }
    
    public Path getBestGuess(){
    	//get paths that fit
    	List<Path> paths = this.getPaths(true);

    	
    	//First extract shortest Path(s)
    	int currentShortest=0;
    	Path bestPath =new Path();
    	double currentHighestSd = 100.0 ;
    	if (paths.size()>0){
    		currentShortest = paths.get(0).size();
    	}
    	for (int i=0;i<paths.size();i++){
    		int size = paths.get(i).size();
        	//System.out.println(size + "   " + paths.get(i));	
    		if (size<=currentShortest && paths.get(i).size()>0){
    			currentShortest = size;
        		bestPath = paths.get(i);
        		currentHighestSd = bestPath.getSd();
    		}
    	}

   	
    	for (Path p : paths){
    		if (p.getSd()<=currentHighestSd && p.getSd()>0 && p.size()<=currentShortest){
    			bestPath = p;
    			currentHighestSd = bestPath.getSd();
    		}
    	}
    	
    	return bestPath;
    }

	public void setLetterSequence(String l) {
		_letterSequence = l;
	}
	

    
}